package xyf.p04.tree;

import commons.TreeNode;

/**
 * ClassName: P0236_LowestCommonAncestor
 * Description:
 * Author: xyf
 * Date: 9/8/22 6:20 PM
 * Version: 1.0
 **/
public class P0236_LowestCommonAncestor
{
    private TreeNode res = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        dfs(root, p, q);
        return res;
    }

    private int dfs(TreeNode root, TreeNode p, TreeNode q)
    {
        if (root == null)
        {
            return 0;
        }

        int left = dfs(root.left, p, q);

        int right = dfs(root.right, p, q);

        int rootVal = 0;

        if (root == p || root == q)
        {
            rootVal = 1;
        }

        if (rootVal == 1 && (left == 1 || right == 1))
        {
            res = root;
        }

        if (rootVal == 0 && left == 1 && right == 1)
        {
            res = root;
        }

        return rootVal + left + right;
    }
}